cells = {}
cells.Size = 28672
Cells = {}
local ENT = FindMetaTable( "Entity" )
local PLY = FindMetaTable( "Player" )

--[[--------------------------------------
FUNCTION: cells.GetConstrainedEnts( e )	--
AUTHOR: aVoN, Tad2020					--
DESC: Gets all ents constrained to the	--
	specified ent						--
----------------------------------------]]
function cells.GetConstrainedEnts(ent,max_passes,passes,entities,cons)
	if(not ValidEntity(ent)) then return {},{} end;
	local entities,cons = (entities or {}),(cons or {});
	local passes = (passes or 0)+1;
	if(max_passes and passes > max_passes) then return end;
	if(not entities[ent]) then
		if(not constraint.HasConstraints(ent)) then return {},{} end;
		entities[ent] = ent;
		for _,v in pairs(ent.Constraints) do
			if(not cons[v]) then
				cons[v] = v;
				for i=1,6 do
					local e = v["Ent"..i];
					if(e) then
						if(e:IsValid()) then
							cells.GetConstrainedEnts(e,max_passes,passes,entities,cons);
						elseif(not entities[e] and e:IsWorld()) then
							entities[e] = e;
						end
					end
				end
			end
		end
	end
	return table.ClearKeys(entities),table.ClearKeys(cons);
end

--[[----------------------------------------------
FUNCTION: cells.GetConstrainedEntsWithSelf( e )	--
AUTHOR: Philpax									--
DESC: Wrapper for GetConstrainedEnts that		--
	returns original ent if no ents found		--
------------------------------------------------]]
function cells.GetConstrainedEntsWithSelf( ent )
	local entities, cons = cells.GetConstrainedEnts( ent )
	if table.Count( entities ) == 0 or entities == nil then
		entities = {}
		table.insert( entities, ent )
	end
	return entities, cons
end

--[[------------------------------------------
FUNCTION: cells.AbsoluteToLocal( pos )		--
AUTHOR: theJ89								--
DESC: When given a cell position, will		--
	return the cell that position is in		--
	as well as the 'local position'			--
	within that cell. 						--
											--
	Inverse of cells.LocalToAbsolute( pos )	--
--------------------------------------------]]
function cells.AbsoluteToLocal( pos )
	local cellPos = Cell( math.Round( pos.X / cells.Size ), math.Round( pos.Y / cells.Size ), math.Round( pos.Z / cells.Size ) )
	local localPos = pos - cellPos:ToVector() * cells.Size
	return cellPos, localPos
end

--[[----------------------------------------------
FUNCTION: cells.LocalToAbsolute( cell, pos )	--
AUTHOR: Philpax									--
DESC: When given a cell and a 'local position'	--
	within that cell, will convert it to an		--
	absolute position.							--
												--
	Inverse of cells.AbsoluteToLocal( pos )		--
------------------------------------------------]]
function cells.LocalToAbsolute( cell, pos )
	return cell:ToVector( ) * cells.Size + pos
end

--[[--------------------------------------
FUNCTION: cells.VectorToCell( vec )		--
AUTHOR: Philpax							--
DESC: Converts a vector to a cell		--
----------------------------------------]]
function cells.VectorToCell( vec )
	return Cell( vec.x, vec.y, vec.z )
end

--[[----------------------------------------------------------
FUNCTION: cells.TestForRepeat( ent1, ent2, cell1, cell2 )	--
AUTHOR: Philpax												--
DESC: Returns true if an object is in a given cell			--
------------------------------------------------------------]]
function cells.TestForRepeatNormal( CR, cell1, cell2 )
	if !CR[1] and cell1.X != cell2.X then return false end
	if !CR[2] and cell1.Y != cell2.Y then return false end
	if !CR[3] and cell1.Z != cell2.Z then return false end
	
	return true
end

function cells.TestForRepeatMinMax( cellMin, cellMax, cell )
	if cell.X > cellMax.X or cell.X < cellMin.X then return false end
	if cell.Y > cellMax.Y or cell.Y < cellMin.Y then return false end
	if cell.Z > cellMax.Z or cell.Z < cellMin.Z then return false end

	return true
end

function cells.TestForRepeat_P( cell1, cell2, CR, cellMin, cellMax )
	if !cellMin:IsZero() or !cellMax:IsZero() then
		return cells.TestForRepeatMinMax( cellMin, cellMax, cell2 )
	else
		return cells.TestForRepeatNormal( CR, cell1, cell2 )
	end
end

function cells.TestForRepeat( ent1, ent2 )
	if ent1:IsValid() and ent2:IsValid() then
		local cell1
		local cell2
		local CR
		local cellMin
		local cellMax
		--[[if SERVER then
			cell1 = ent1.Cell or cell_origin
			cell2 = ent2.Cell or cell_origin
			CR = ent1.CellRepeat or {false,false,false}
			cellMin = ent1.CellRepeatMin or cell_origin
			cellMax = ent1.CellRepeatMax or cell_origin
		else]]
			cell1 = ent1:GetCell()
			cell2 = ent2:GetCell()
			CR = ent1:GetCellRepeat()
			cellMin = ent1:GetCellRepeatMin()
			cellMax = ent1:GetCellRepeatMax()
		--end

		return cells.TestForRepeat_P( cell1, cell2, CR, cellMin, cellMax )
	end
end

local prohibitedEntities = { viewmodel = 1, predicted_viewmodel = 1, physgun_beam = 1, worldspawn = 1 }
--[[--------------------------------------------------
FUNCTION: cells.Collide( ent1, ent2 )				--
HOOK: ShouldCollide									--
AUTHOR: Philpax										--
DESC: Determines whether two entities should collide--
----------------------------------------------------]]
function cells.Collide( ent1, ent2 )
	if prohibitedEntities[ent1:GetClass()] != nil or prohibitedEntities[ent2:GetClass()] != nil then
		return
	end

	if !cells.TestForRepeat( ent1, ent2 ) and !cells.TestForRepeat( ent2, ent1 ) then
		return false
	end
end
hook.Add( "ShouldCollide", "cells.Collide", cells.Collide )

--[[--------------------------------------------------
FUNCTION: cells.ReturnAllNotInCell( cell )			--
AUTHOR: Philpax										--
DESC: Returns all the entities NOT in a given cell	--
----------------------------------------------------]]
function cells.ReturnAllNotInCell( cell )
	local entities = {}
	local entitiesInCell = Cells[ tostring(cell) ]

	if entitiesInCell == nil then return ents.GetAll() end

	for k,v in pairs( ents.GetAll() ) do
		if entitiesInCell[v:EntIndex()] == nil then
			entities[ v:EntIndex() ] = v
		end
	end

	return entities
end

--[[--------------------------------------------------
FUNCTION: cells.ReturnAllInCell( cell )				--
AUTHOR: Philpax										--
DESC: Returns all the entities in a given cell		--
----------------------------------------------------]]
function cells.ReturnAllInCell( cell )
	return Cells[ tostring(cell) ]
end

--[[--------------------------------------------------
FUNCTION: cells.ReturnRepeatingEntities()			--
AUTHOR: Philpax										--
DESC: Returns all the entities in a given cell		--
----------------------------------------------------]]
function cells.ReturnRepeatingEntities( )
	local entities = {}
	for k,v in pairs( ents.GetAll() ) do
		local CR = v:GetCellRepeat()

		if CR[1] != false or CR[2] != false or CR[3] != false then
			table.insert( entities, v )
		end
	end
	
	return entities
end

--[[--------------------------------------------------
FUNCTION: ENT:GetCell( )							--
AUTHOR: Philpax										--
DESC: Gets the current cell of an entity			--
----------------------------------------------------]]
function ENT:GetCell( )
	--if SERVER then
	--	return self.Cell or cell_origin
	--end

	return Cell( self:GetNetworkedInt( "Cell_X" ), self:GetNetworkedInt( "Cell_Y" ), self:GetNetworkedInt( "Cell_Z" ) )
end

--[[--------------------------------------------------
FUNCTION: ENT:GetCellRepeat()						--
AUTHOR: Philpax										--
DESC: Gets the cell repeat status of an entity		--
----------------------------------------------------]]
function ENT:GetCellRepeat( )
	--if SERVER then
	--	return self.CellRepeat or {false,false,false}
	--end
	return { self:GetNetworkedBool( "CellRepeat_X" ), self:GetNetworkedBool( "CellRepeat_Y" ), self:GetNetworkedBool( "CellRepeat_Z" ) }
end

function ENT:GetCellRepeatMin( )
	--if SERVER then
	--	return self.CellRepeatMin or cell_origin
	--end
	local crmX = self:GetNetworkedInt( "CellRepeatMin_X" ) or 0
	local crmY = self:GetNetworkedInt( "CellRepeatMin_Y" ) or 0
	local crmZ = self:GetNetworkedInt( "CellRepeatMin_Z" ) or 0

	return Cell( crmX, crmY, crmZ )
end

function ENT:GetCellRepeatMax( )
	--if SERVER then
	--	return self.CellRepeatMax or cell_origin
	--end
	local crmX = self:GetNetworkedInt( "CellRepeatMax_X" ) or 0
	local crmY = self:GetNetworkedInt( "CellRepeatMax_Y" ) or 0
	local crmZ = self:GetNetworkedInt( "CellRepeatMax_Z" ) or 0

	return Cell( crmX, crmY, crmZ )
end

--[[--------------------------------------------------
FUNCTION: ENT:GetCellPos( )							--
AUTHOR: Philpax										--
DESC: Gets the current position of an entity 		--
	compensated for the cell; may be used as GetPos	--
	override in future - sorry, I mean, now!		--
----------------------------------------------------]]
ENT.GetPos_cell = ENT.GetPos
function ENT:GetCellPos( )
	return cells.LocalToAbsolute( self:GetCell(), self:GetPos_cell() )
end

--[[--------------------------------------------------
FUNCTION: ENT:GetPos( )								--
AUTHOR: Philpax										--
DESC: Let's get funky and override GetPos! + Hacks	--
----------------------------------------------------]]
local clNoOverride = { "sent_ball" }
local svNoOverride = {}
local shNoOverride = { "gmod_dynamite" }
function cells.GetPosOverride( self )
	if table.HasValue(clNoOverride, self:GetClass()) and CLIENT then
		return self:GetPos_cell()
	end

	if table.HasValue(svNoOverride, self:GetClass()) and SERVER then
		return self:GetPos_cell()
	end

	if table.HasValue(shNoOverride, self:GetClass()) then
		return self:GetPos_cell()
	end

	return self:GetCellPos()
end
ENT.GetPos = cells.GetPosOverride

ENT.EyePos_cell = ENT.EyePos
function cells.EyePosOverride( self )
	local cell = cells.AbsoluteToLocal( self:GetPos() )
	return cells.LocalToAbsolute( cell, self:EyePos_cell() )
end
ENT.EyePos = cells.EyePosOverride
--[[--------------------------------------------------
FUNCTION: util.TraceLine( trace )					--
AUTHOR: Philpax										--
DESC: Please work. Just. Work. Please.				--
TODO: Across cell transitions. Oh boy.				--
----------------------------------------------------]]
util.TraceLine_cell = util.TraceLine
function util.TraceLine( trace )
	local startCell, startPos = cells.AbsoluteToLocal( trace.start )
	local endPos = startPos + ( ( trace.endpos - trace.start ):Normalize() * (trace.endpos - trace.start):Length() ) -- the original endpos can't be used
	
	--local filter = cells.ReturnAllNotInCell( startCell )
	
	--if type( trace.filter ) != "table" and trace.filter != nil then
	--	table.insert( filter, trace.filter )
	--elseif type( trace.filter ) == "table" then
	--	table.Add( filter, trace.filter )
	--end

	trace.start = startPos
	trace.endpos = endPos
	
	local traceResult = util.TraceLine_cell( trace )
	traceResult.HitPos = cells.LocalToAbsolute( startCell, traceResult.HitPos )

	return traceResult
end

--[[--------------------------------------------------
CLASS/METATABLE: Cell								--
AUTHOR: Philpax										--
DESC: Represents an entity's current cell as a		--
	userdata value that can be manipulated			--
----------------------------------------------------]]
local CELL = {}
local CELL_methods = {}

function CELL:__tostring()
	return tostring(self.X) .. " " .. tostring(self.Y) .. " " .. tostring(self.Z)
end

function CELL:__eq( B )
	if self != nil and B != nil then
		if self.X == B.X and self.Y == B.Y and self.Z == B.Z then return true else return false end
	else
		return nil
	end
end

function CELL:__add( B )
	return Cell( self.X + B.X, self.Y + B.Y, self.Z + B.Z )
end

function CELL:__sub( B )
	return Cell( self.X - B.X, self.Y - B.Y, self.Z - B.Z )
end

function CELL_methods:ToVector( )
	return Vector( self.X, self.Y, self.Z )
end

function CELL_methods:Zero()
	return Cell( 0, 0, 0 )
end

function CELL_methods:IsZero()
	return self.X == 0 and self.Y == 0 and self.Z == 0
end

function CELL_methods:IsPosInsideWithGap( pos, gap )
	if pos.X >= self.lowerBound.X - gap and pos.X <= self.upperBound.X + gap and pos.Y >= self.lowerBound.Y - gap and pos.Y <= self.upperBound.Y + gap and pos.Z >= self.lowerBound.Z - gap and pos.Z <= self.upperBound.Z + gap then return true end
	return false
end

function CELL_methods:IsPosInside( pos )
	if pos.X >= self.lowerBound.X and pos.X <= self.upperBound.X and pos.Y >= self.lowerBound.Y and pos.Y <= self.upperBound.Y and pos.Z >= self.lowerBound.Z and pos.Z <= self.upperBound.Z then return true end
	return false
end

function CELL:__index(key)
	if CELL_methods[key] != nil then return CELL_methods[key] end
end

function Cell( CellX, CellY, CellZ )
	local cell = { X = CellX, Y = CellY, Z = CellZ }
	cell.lowerBound = Vector( cells.Size * (cell.X - 0.5), cells.Size * (cell.Y - 0.5), cells.Size * (cell.Z - 0.5) )
	cell.upperBound = Vector( cells.Size * (cell.X + 0.5), cells.Size * (cell.Y + 0.5), cells.Size * (cell.Z + 0.5) )
	setmetatable( cell, CELL )
	return cell
end
_R.Cell = CELL

cell_origin = Cell( 0, 0, 0 )